{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Power of Two"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #recursion #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #递归 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: isPowerOfTwo"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #2 的幂"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数 <code>n</code>，请你判断该整数是否是 2 的幂次方。如果是，返回 <code>true</code> ；否则，返回 <code>false</code> 。</p>\n",
    "\n",
    "<p>如果存在一个整数 <code>x</code> 使得 <code>n == 2<sup>x</sup></code> ，则认为 <code>n</code> 是 2 的幂次方。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 1\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>2<sup>0</sup> = 1\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 16\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>2<sup>4</sup> = 16\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 3\n",
    "<strong>输出：</strong>false\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 4\n",
    "<strong>输出：</strong>true\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 5：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 5\n",
    "<strong>输出：</strong>false\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>-2<sup>31</sup> <= n <= 2<sup>31</sup> - 1</code></li>\n",
    "</ul>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>进阶：</strong>你能够不使用循环/递归解决此问题吗？</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [power-of-two](https://leetcode.cn/problems/power-of-two/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [power-of-two](https://leetcode.cn/problems/power-of-two/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['1', '16', '3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPowerOfTwo(self, n: int) -> bool:\n",
    "        # should remember to consider about the negative number.\n",
    "        if n <= 0:\n",
    "            return False\n",
    "    \n",
    "        while n > 1:\n",
    "            if (n / 2) % 2 != 0 and n != 2:\n",
    "                return False\n",
    "            n = n / 2\n",
    "        return True\n",
    "        \n",
    "        # more easier\n",
    "        # if n <= 0:\n",
    "        #     return False\n",
    "        # while n % 2 == 0:\n",
    "        #     n /= 2\n",
    "        # return n == 1\n",
    "        \n",
    "        # or use binary operations\n",
    "        # if n <= 0:\n",
    "        #     return False\n",
    "        # return n & (-n) == n  or return n & (n - 1) == 0\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def isPowerOfTwo(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if n < 1:\n",
    "            return False\n",
    "        while n != 1:\n",
    "            n1 = n / 2\n",
    "            n2 = n >> 1\n",
    "            if n1 != n2:\n",
    "                return False\n",
    "            n = int(n1)\n",
    "        return True\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPowerOfTwo(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if n==0:return False\n",
    "        while n:\n",
    "            if n==1:return True\n",
    "            if n/2!=int(n/2):\n",
    "                return False\n",
    "            n=n/2\n",
    "            \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPowerOfTwo(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        #2的幂次方与 其-1 异或\n",
    "        if n==1:\n",
    "            return True\n",
    "        if n==0:\n",
    "            return False\n",
    "        m = n-1\n",
    "        result = n&m\n",
    "\n",
    "        print(result)\n",
    "        return False if result else True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPowerOfTwo(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if n <= 0 : return False \n",
    "        if n <= 2 : return True\n",
    "        while n != 0 and n!=1:\n",
    "            print (n)\n",
    "            if n%2 == 0:\n",
    "                n = n//2\n",
    "            else:\n",
    "                return False \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPowerOfTwo(self, n: int) -> bool:\n",
    "        if n <= 0:\n",
    "            return False\n",
    "        return (n & (n - 1)) == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPowerOfTwo(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        # if n <=0:\n",
    "            # return False\n",
    "#         for i in range(31):\n",
    "#             if n /2 == 1 or n//2 == 0:\n",
    "#                 return True\n",
    "#             elif n%2 == 0:\n",
    "#                 n = n/2\n",
    "#             else:\n",
    "#                 return False\n",
    "        return n >0 and not (n & (n-1))\n",
    "        \n",
    "    \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPowerOfTwo(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        return n != 0 and n & (n - 1) == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPowerOfTwo(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if n <= 0:\n",
    "            return False\n",
    "        else:\n",
    "            from math import log\n",
    "            if 2 ** round(log(n, 2)) == n:\n",
    "                return True\n",
    "            else:\n",
    "                return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPowerOfTwo(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if n < 0:\n",
    "            return(False)\n",
    "        a = bin(n).replace(\"0b\",\"\")\n",
    "        \n",
    "        print(a)\n",
    "        if a.count(\"1\") == 1:\n",
    "            return(True)\n",
    "        else:\n",
    "            return(False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPowerOfTwo(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        tlist = [2 ** i for i in range(65)]\n",
    "        if n in tlist:\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPowerOfTwo(self, n: int) -> bool:\n",
    "        if n==1:\n",
    "            return True\n",
    "        if bin(n)[2]=='1' :\n",
    "            if '1' not in bin(n)[3:]:\n",
    "                return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPowerOfTwo(self, n: int) -> bool:\n",
    "        return n > 0 and not n & (n - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPowerOfTwo(self, n: int) -> bool:\n",
    "        \n",
    "        # while n > 1:\n",
    "        #     n /= 2\n",
    "        # return n == 1\n",
    "\n",
    "        # ##按位计算\n",
    "        # return n > 0 and n & (n-1) == 0\n",
    "\n",
    "        # ## 提前结束\n",
    "        # if n <= 0:\n",
    "        #     return False\n",
    "        # while n % 2 == 0:\n",
    "        #     n /= 2\n",
    "        # return n == 1\n",
    "\n",
    "        if n <= 0:\n",
    "            return False\n",
    "        return n & (-n) == n\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPowerOfTwo(self, n: int) -> bool:\n",
    "        if n <= 0:\n",
    "            return False\n",
    "        while(n > 1):\n",
    "            noun = n % 2\n",
    "            n = n // 2\n",
    "            if noun == 1:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPowerOfTwo(self, n: int) -> bool:\n",
    "        while n >1:\n",
    "                if n%2!=0:\n",
    "                    return False\n",
    "                    break\n",
    "                n=n/2\n",
    "        if n ==1:\n",
    "                return True\n",
    "        else:\n",
    "                return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPowerOfTwo(self, n: int) -> bool:\n",
    "        res = 1\n",
    "        while res < n:\n",
    "            res *= 2\n",
    "        if res == n:\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPowerOfTwo(self, n: int) -> bool:\n",
    "        \n",
    "        if n<=0:\n",
    "            return False\n",
    "        if (n&(n-1)==0):\n",
    "            return True             \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPowerOfTwo(self, n: int) -> bool:\n",
    "        return n>0 and n&(n-1) == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPowerOfTwo(self, n: int) -> bool:\n",
    "        if n>=0:\n",
    "            a=int(n**0.5)\n",
    "            for i in range(0,a+2):\n",
    "                print(i)\n",
    "                if 2**i==n:\n",
    "                    print(i)\n",
    "                    return True\n",
    "            else:\n",
    "                print('no')\n",
    "                return False\n",
    "        else:\n",
    "            b=-n\n",
    "            a=int(b**0.1)\n",
    "            for i in range(-a,0):\n",
    "                print(i)\n",
    "                if 2**i==n:\n",
    "                    print(i)\n",
    "                    return True\n",
    "            else:\n",
    "                print('no')\n",
    "                return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPowerOfTwo(self, n: int) -> bool:\n",
    "        if n == 1:\n",
    "            return True\n",
    "        elif 1 < n < 2 or n == 0:\n",
    "            return False\n",
    "        return self.isPowerOfTwo(n / 2) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://leetcode.com/problems/power-of-two/\n",
    "import os, sys, shutil, glob, re\n",
    "import time, calendar\n",
    "from datetime import datetime, timezone\n",
    "import hashlib, zipfile, zlib\n",
    "from math import *\n",
    "from operator import itemgetter\n",
    "from functools import wraps, cmp_to_key, reduce\n",
    "from itertools import count, combinations, permutations\n",
    "from collections import namedtuple, defaultdict, Counter, deque\n",
    "from queue import Queue\n",
    "from bisect import bisect_left, bisect_right\n",
    "\n",
    "def refreshGlobals():\n",
    "  pass\n",
    "\n",
    "refreshGlobals()\n",
    "\n",
    "class Solution:\n",
    "    def isPowerOfTwo(self, n): # -> bool\n",
    "      if n == 0:\n",
    "        return False\n",
    "      return bool(not n & (n-1))\n",
    "\n",
    "\n",
    "if __name__ == '__main__' and ('SJDEAK' in os.environ):\n",
    "  from utils.tree import TreeNode, array2TreeNode\n",
    "\n",
    "  def test(*args):\n",
    "    print('输入数据: ', *args)\n",
    "    print('结果: ', Solution().isPowerOfTwo(*args), end='\\n-----\\n')\n",
    "\n",
    "\n",
    "  test(0)\n",
    "  test(1)\n",
    "  test(16)\n",
    "  test(218)\n",
    "else:\n",
    "  print = lambda *args, **kwargs: None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPowerOfTwo(self, n: int) -> bool:\n",
    "        res=0\n",
    "        while n>0:\n",
    "            res+=n&1\n",
    "            n=n>>1\n",
    "        return res==1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPowerOfTwo(self, n: int) -> bool:\n",
    "        return n.bit_count()==1 and n>0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPowerOfTwo(self, n: int) -> bool:\n",
    "       return n > 0 and n & (n-1) ==0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPowerOfTwo(self, n: int) -> bool:\n",
    "        for i in range(-31,32):\n",
    "            if 2 ** i == n: return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPowerOfTwo(self, n: int) -> bool:\n",
    "        if n == 1:\n",
    "            return True\n",
    "\n",
    "        def dfs(i):\n",
    "            if i == 2:\n",
    "                return True\n",
    "            # if type(i/2) != type(int):\n",
    "            #     return False\n",
    "            if i < 2:\n",
    "                return False\n",
    "            return dfs(i/2)\n",
    "        return dfs(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPowerOfTwo(self, n: int) -> bool:\n",
    "        if n%2==1 and n>1:\n",
    "            return False \n",
    "        if n==0:\n",
    "            return False\n",
    "        if n==1:\n",
    "            return True\n",
    "        return self.isPowerOfTwo(n/2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPowerOfTwo(self, n: int) -> bool:\n",
    "        if n <= 0:\n",
    "            return False\n",
    "        return n & (n - 1) == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def isPowerOfTwo(self, n: int) -> bool:\n",
    "        return n>0 and bin(n).count(\"1\")==1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPowerOfTwo(self, n: int) -> bool:\n",
    "        return n > 0 and n & (n - 1) == 0"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
